/* 上下界可行流

* 本题:
    //保证流量平衡
    if(last < 0) AddEdge(i, T, -last, 0); 
    c出-c入 |last|(-last)是当天人员不够的数量
    流出(-last),为保证流量平衡，需要流入(-last)，即需要数量

    else if(last > 0) AddEdge(S, i, last, 0); 
    c入-c出 last是当天人员超出的数量 
    流入前几天总计超出人员的数量，保证流量平衡
    源点S表示所有可能的志愿者来源
    流入last,为保证流量平衡，需要流出last，即多余数量

    (ti+1, si, INF, ci) //流量平衡 这条边的流量即为该类志愿者的人数 容量INF, 费用是该类志愿者的费用
    
    i->i+1 的流量为第i天需要的人数
    故最小费用最大流即为所求

*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 1010, M = 30010, INF=0x3f3f3f3f;
int n, m, S, T; //天数 点数 虚拟源汇点
int h[N], e[M], c[M], w[M], ne[M], idx;
int q[N], pre[N], incf[N], d[N];
bool st[N];

void AddEdge(int a, int b, int cc, int ww)
{
    //printf("%d->%d %d %d\n", a, b, cc, ww);
    e[idx]=b, c[idx]=cc, w[idx]=ww, ne[idx]=h[a], h[a]=idx++;
    e[idx]=a, c[idx]=0, w[idx]=-ww, ne[idx]=h[b], h[b]=idx++;
}

bool spfa()
{
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    int hh=0, tt=0;
    q[tt++]=S, d[S]=0, incf[S]=INF;
    while(hh!=tt)
    {
        int u=q[hh++];
        if(hh==N) hh=0;
        st[u]=false;
        for(int i=h[u]; ~i; i=ne[i])
        {
            int v=e[i];
            if(c[i] && d[v]>d[u]+w[i])
            {
                d[v]=d[u]+w[i];
                pre[v]=i;
                incf[v]=min(incf[u], c[i]);
                if(!st[v])
                {
                    q[tt++]=v;
                    if(tt==N) tt=0;
                    st[v]=true;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int cost = 0;
    while(spfa())
    {
        cost += incf[T]*d[T];
        //printf("cost:%d\n", cost);
        for(int i=T; i!=S; i=e[pre[i]^1])
        {
            c[pre[i]]-=incf[T]; c[pre[i]^1]+=incf[T];
        }
    }
    return cost;
}


signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
    #else
        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif

    memset(h, -1, sizeof h);

    cin >> n >> m; //边数 点数
    S=0, T=n+2; 

    int last = 0; //记录流量差值
    for(int i = 1; i<=n; i++)
    {
        int c; cin >> c;
        //printf("%d %d\n", c, last);
        last -= c;

        //保证流量平衡
        if(last < 0) AddEdge(i, T, -last, 0); 
        else if(last > 0) AddEdge(S, i, last, 0); 

        AddEdge(i, i+1, INF-c, 0); //流量下界是A[i], 上界INF-c, 费用0，流量为第i天的工作人数
        last = c;
    }

    AddEdge(S, n+1, last, 0); //剩余人数

    for(int i = 1; i<=m; i++)
    {
        int si, ti, ci; cin >> si >> ti >> ci;
        AddEdge(ti+1, si, INF, ci); 
    }

    printf("%d\n", EK());
    return 0;
}